package u1;

import static java.lang.System.*;
import static u1.Util.*;
import gnu.trove.TIntHashSet;
import gnu.trove.TIntIterator;
import gnu.trove.decorator.TIntHashSetDecorator;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * From a set of starting nodes, follow one level of links (and following any
 * redirects) in a given adjacency list. The result is the set of nodes that are
 * reachable in one step (not counting redirects) from the start set.
 * 
 * Takes the adjacency list on standard in. Takes the name of a file containing
 * a list of node numbers, delimited by whitespace, to start from as the first
 * argument. Takes the name of a file containing a list of redirect node
 * numbers and the node numbers they redirect to, delimited by whitespace, that
 * tell the grower what nodes are redirect nodes. Produces the resulting node
 * list on standard out, one node number per line.
 */
public class Grow {
  public static void main(String[] args) throws FileNotFoundException {
    if (args.length != 2) {
      err.println("See comments for usage.");
      exit(-1);
    }

    String startFile = args[0];
    String redirectFile = args[1];

    /*
     * Scan start nodes.
     */
    trace("Reading start nodes from %s...", startFile);
    Scanner startScanner = new Scanner(new File(startFile));
    ArrayList<Integer> start = new ArrayList<Integer>(PAGES_MAX);
    while (startScanner.hasNextInt()) {
      start.add(startScanner.nextInt());
    }
    startScanner.close();
    trace("Got %d start nodes.", start.size());

    /*
     * Scan redirect nodes.
     */
    trace("Reading redirects from %s...", redirectFile);
    Scanner redirectScanner = new Scanner(new File(redirectFile));
    Map<Integer,Integer> redirects = new HashMap<Integer,Integer>();
    while (redirectScanner.hasNextInt()) {
      int redirectSource = redirectScanner.nextInt();
      assert(redirectScanner.hasNextInt());
      int redirectTarget = redirectScanner.nextInt();
      redirects.put(redirectSource, redirectTarget);
    }
    redirectScanner.close();
    trace("Got %d redirects.", redirects.size());

    Grow g = new Grow(in, start, redirects, PAGES_MAX);

    for (Integer i : g.getResult()) {
      out.println(i);
    }
  }

  private Set<Integer> result;

  /**
   * @param adjIS
   *                not null
   * @param start
   *                not null; contents changed by this method.
   * @param redirects
   *                not null; contents changed by this method. These links are
   *                always followed if they are encountered.
   * @param initialHashCapacity
   *                positive; set to ~ number of pages expected
   */
  public Grow(InputStream adjIS, Collection<Integer> start,
      Map<Integer, Integer> redirects, int initialHashCapacity) {

    // Load the whole adjacency map into memory.
    trace("Reading adjacency list...");
    Map<Integer, Set<Integer>> adj = AdjReader
        .loadT(adjIS, initialHashCapacity);
    trace("Read %d pages in adjacency list.", adj.size());

    /*
     * Start by following all redirects from the start nodes. We get those for
     * free. We may have multiple levels of redirects (but probably not many),
     * so we should do this iteratively (but not a big deal).
     */
    trace("Following redirects from %d start pages...", start.size());
    followRedirects(start, redirects, initialHashCapacity);

    /*
     * Now start following links. An average page has about 10 links, so we make
     * the result set about 10x bigger than the start set.
     */
    trace("Following links from %d pages...", start.size());
    result = new TIntHashSetDecorator(new TIntHashSet(10 * start.size()));
    for (Integer i : start) {
      result.addAll(adj.get(i));
    }
    trace("Got %d new pages by following links.", result.size());

    /*
     * Each link that we followed might be a redirect. We follow all redirect
     * links in the result set, as we did in the start set.
     */
    trace("Following redirects from %d pages...", result.size());
    followRedirects(result, redirects, initialHashCapacity);

    /*
     * Don't forget the start set.
     */
    result.addAll(start);
    trace("Finished with %d pages.", result.size());
  }

  /**
   * Follow all redirects from base.
   * 
   * @param base
   *                not null; start from these nodes and add any nodes that are
   *                found to this collection.
   * @param redirects
   *                not null
   * @param adj
   *                not null
   */
  private void followRedirects(Collection<Integer> base,
      Map<Integer,Integer> redirects, int initialHashCapacity) {
    TIntHashSet next = new TIntHashSet(initialHashCapacity);

    do {
      next.clear();
      for (Integer i : base)
        if (redirects.containsKey(i))
          next.add(redirects.get(i));
      for (Integer i : base)
        next.remove(i);
      trace("Got %d new pages by following redirects.", next.size());
      TIntIterator it = next.iterator();
      while (it.hasNext())
        base.add(it.next());
    } while (!next.isEmpty());
  }

  public Set<Integer> getResult() {
    return result;
  }
}
/*
* Copyright (c) 2009 John Lees-Miller
* 
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/

